1. Field of the Invention
The present invention relates generally to data transfer and, more particularly, to systems and methods for preserving the order of blocks of data processed by one or more processing paths in a data processing system.
2. Description of Related Art
In a data processing or communications system that must deliver high throughput in processing or communicating a stream of data, an existing point-to-point approach is to provide n independent processing paths and distribute sub-streams of the data down each of the n paths. After processing by each of the processing paths, the sub-streams are recombined to create an output stream. A problem that arises using this approach is that the different processing paths may have different delays. As a result, if a first block of data (e.g., a packet or cell) is sent down a first path at time t1 and a second block of data is sent down a second path at time t2>t1, the second block of data may nonetheless finish being processed before the first. Therefore, if nothing is done to correct for this differential delay, the recombined stream of data will be out-of-order relative to the input stream. Out-of-order blocks of data can be problematic in a number of data processing applications.
Out-of-order blocks of data are particularly difficult to prevent in an “any-to-any” situation, when there are R input streams connected to S output streams via n processing paths. In the any-to-any situation, blocks of data are distributed across the n processing paths prior to determining the output destination. The processing paths determine the appropriate output destination.
According to the any-to-any situation, different blocks of data from an input stream can be destined for different output streams. The blocks of data of each input stream are distributed across the processing paths and then concentrated back to the desired output stream, possibly resulting in out-of-order streams. Algorithms exist for restoring order to out-of-order streams at recombination time, based on attaching sequence numbers to consecutive blocks at the input, and sorting blocks to restore consecutive sequence numbers at the output. In the any-to-any situation, however, a given output will not receive all sequence numbers from a given input, making existing sorting algorithms impractical.
Therefore, there exists a need for systems and methods that preserve the order of blocks of data in data streams that have been distributed across one or more paths in a data processing system.